package LeetCode._01算法入门.day05双指针;

import org.junit.Test;

/**
 * @author 挚爱之夕
 * @date 2022-02-24 - 02 - 24 - 15:52
 * @Description 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 * @Version 1.0
 */
public class _876链表的中间节点 {
    static ListNode head1;//奇数个 0->1->2->3->4
    static ListNode head2;//偶数个 0->1->2->3->4->5->6->7
    static {
        head1 = new ListNode(0);
        ListNode listNode1 = new ListNode(1);
        head1.next = listNode1;
        ListNode listNode2 = new ListNode(2);
        listNode1.next = listNode2;
        ListNode listNode3 = new ListNode(3);
        listNode2.next = listNode3;
        listNode3.next = new ListNode(4);

        head2 = new ListNode(0);
        ListNode p = head2;
        for (int i = 1; i < 8; i++) {
            p.next = new ListNode(i);
            p = p.next;
        }
    }
    //by me 快慢指针
    @Test
    public void solve(){
        ListNode res = middleNode(head1);//中间节点1个，返回2
        System.out.println(res);

        ListNode res2 = middleNode(head2);//中间节点有3和4，返回4
        System.out.println(res2);
    }
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    //单指针 两次遍历
    public ListNode middleNode1(ListNode head) {
        ListNode cur = head;
        int length = 0;
        //得到链表长度
        while(cur != null){
            cur = cur.next;
            length++;
        }
        cur = head;
        //返回中间节点
        int k = 0;
        while(k < length / 2){
            k++;
            cur = cur.next;
        }
        return cur;
    }
}
class ListNode{
    int val;
    ListNode next;
    ListNode(){}

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        ListNode n = this;
        StringBuilder sb = new StringBuilder();
        sb.append(val);
        while((n = n.next) != null){
            sb.append("->").append(n.val);
        }
        return sb.toString();
    }
}
